/**
 * Copyright (c) 2008-2009, Markos Evlogimenos
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in
 *       the documentation and/or other materials provided with the
 *       distribution.
 *     * The name of Markos Evlogimenos may be used to endorse or
 *		 promote products derived from this software without specific
 *		 prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.kamimark.collections;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

@SuppressWarnings("unchecked")
public class IDSortedList<E extends _Identifiable> implements Collection<E>, List<E>
{
	private List<E> data;

	/** Make sure the List passed is sorted */
	public IDSortedList(List<E> data) {
		this.data = data;
	}

	public boolean add(E o) {
		return binaryAdd(o);
	}

	private int binaryIDSearch(int id) {
		int low = 0;
		for (int high = data.size() - 1; low <= high;) {
			int mid = low + high >> 1;
			E midslot = data.get(mid);
			if (midslot == null) {
				low++;
				continue;
			}
			int diff = midslot.getID() - id;
			if (diff < 0)
				low = mid + 1;
			else if (diff > 0)
				high = mid - 1;
			else
				return mid;
		}
		return -1;
	}

	private int binarySearch(E obj) {
		int low = 0;
		for (int high = data.size() - 1; low <= high;) {
			int mid = low + high >> 1;
			E midslot = data.get(mid);
			if (midslot == null) {
				low++;
				continue;
			}
			int diff = midslot.compareTo(obj);
			if (diff < 0)
				low = mid + 1;
			else if (diff > 0)
				high = mid - 1;
			else
				return mid;
		}

		return -(low + 1);
	}

	private boolean binaryAdd(E obj) {
		int low = 0;
		for (int high = data.size() - 1; low <= high;) {
			int mid = low + high >> 1;
			E midslot = data.get(mid);
			if (midslot == null) {
				low++;
				continue;
			}
			int diff = midslot.compareTo(obj);
			if (diff < 0)
				low = mid + 1;
			else if (diff > 0)
				high = mid - 1;
			else
				return false; // Object exists
		}
		data.add(low, obj);
		return true;
	}

	public boolean addAll(Collection<? extends E> c) {
		for (E o : c)
			if (!add(o))
				return false;
		return true;
	}

	public void clear() {
		data.clear();
	}

	public boolean contains(Object obj) {
		return binarySearch((E) obj) > -1;
	}

	public boolean containsAll(Collection<?> collection) {
		for (Object o : collection)
			if (binarySearch((E) o) == -1)
				return false;
		return true;
	}

	public boolean equals(Object obj) {
		return data.equals(obj);
	}

	/** @return the E element at the index i of the list. */
	public E getByIndex(int i) {
		return data.get(i);
	}

	/** @return the E element in the list with matching ID */
	public E get(int id) {
		int index = binaryIDSearch(id);
		if (index == -1)
			return null;
		return data.get(index);
	}

	public int hashCode() {
		return data.hashCode();
	}

	public int indexOf(Object obj) {
		return binarySearch((E) obj);
	}

	public boolean isEmpty() {
		return data.isEmpty();
	}

	public Iterator<E> iterator() {
		return data.iterator();
	}

	public ListIterator<E> listIterator() {
		return data.listIterator();
	}

	public ListIterator<E> listIterator(int i) {
		return data.listIterator(i);
	}

	/** Removes an element by it's ID */
	public E remove(int id) {
		if (data.size() == 0)
			return null;
		int index = binaryIDSearch(id);
		return data.remove(index);
	}

	public E removeByIndex(int i) {
		return data.remove(i);
	}

	public boolean remove(Object obj) {
		int loc = binarySearch((E) obj);
		if (loc == -1)
			return false;
		remove(loc);
		return true;
	}

	public boolean removeAll(Collection<?> collection) {
		for (Object o : collection) {
			int loc = binarySearch((E) o);
			if (loc == -1)
				return false;
			remove(loc);
		}
		return true;
	}

	public boolean retainAll(Collection<?> arg0) {
		return data.retainAll(arg0);
	}

	public E set(int index, E element) {
		return data.set(index, element);
	}

	public int size() {
		return data.size();
	}

	public List<E> subList(int i, int j) {
		return data.subList(i, j);
	}

	public Object[] toArray() {
		return data.toArray();
	}

	public <T> T[] toArray(T[] a) {
		return data.toArray(a);
	}

	public String toString() {
		return data.toString();
	}

	/**
	 * <p>
	 * Unsupported Operation
	 * </p>
	 * 
	 * @throws UnsupportedOperationException
	 */
	public void add(int index, E element) {
		throw new UnsupportedOperationException();
	}

	/**
	 * <p>
	 * Unsupported Operation
	 * </p>
	 * 
	 * @return false
	 */
	public boolean addAll(int index, Collection<? extends E> c) {
		return false;
	}

	/**
	 * <p>
	 * Exactly the same as IndexOf since no duplicates are allowed.
	 * </p>
	 * 
	 * @return false
	 */
	public int lastIndexOf(Object obj) {
		return indexOf(obj);
	}

}
